{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "from mlxtend.preprocessing import TransactionEncoder\n",
    "from mlxtend.frequent_patterns import fpgrowth\n",
    "from mlxtend.frequent_patterns import association_rules\n",
    "\n",
    "from collections import Counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>index</th>\n",
       "      <th>alg_tags</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>字符串</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>模拟</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2</td>\n",
       "      <td>动态规划,dp</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>3</td>\n",
       "      <td>模拟&amp;枚举</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>4</td>\n",
       "      <td>动态规划,dp&amp;递归&amp;费用流</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   index        alg_tags\n",
       "0      0             字符串\n",
       "1      1              模拟\n",
       "2      2         动态规划,dp\n",
       "3      3           模拟&枚举\n",
       "4      4  动态规划,dp&递归&费用流"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alg_tags_df = pd.read_csv('problem_list.csv')['alg_tags'].reset_index()\n",
    "alg_tags_df.dropna(inplace=True)\n",
    "\n",
    "alg_tags_df.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>index</th>\n",
       "      <th>alg_tags</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0</td>\n",
       "      <td>[字符串]</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>[模拟]</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>2</td>\n",
       "      <td>[动态规划,dp]</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>3</td>\n",
       "      <td>[模拟, 枚举]</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>4</td>\n",
       "      <td>[动态规划,dp, 递归, 费用流]</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   index            alg_tags\n",
       "0      0               [字符串]\n",
       "1      1                [模拟]\n",
       "2      2           [动态规划,dp]\n",
       "3      3            [模拟, 枚举]\n",
       "4      4  [动态规划,dp, 递归, 费用流]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alg_tags_df['alg_tags'] = alg_tags_df['alg_tags'].apply(lambda row: row.split('&'))\n",
    "\n",
    "alg_tags_df.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>tag</th>\n",
       "      <th>freq</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>动态规划,dp</td>\n",
       "      <td>923</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>数学</td>\n",
       "      <td>721</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>模拟</td>\n",
       "      <td>598</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>枚举</td>\n",
       "      <td>549</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>贪心</td>\n",
       "      <td>506</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>169</th>\n",
       "      <td>链表</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>165</th>\n",
       "      <td>快速莫比乌斯变换 FMT</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>154</th>\n",
       "      <td>点积</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>119</th>\n",
       "      <td>哈夫曼树</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>204</th>\n",
       "      <td>笛卡尔树</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>205 rows × 2 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "              tag  freq\n",
       "2         动态规划,dp   923\n",
       "9              数学   721\n",
       "1              模拟   598\n",
       "3              枚举   549\n",
       "8              贪心   506\n",
       "..            ...   ...\n",
       "169            链表     1\n",
       "165  快速莫比乌斯变换 FMT     1\n",
       "154            点积     1\n",
       "119          哈夫曼树     1\n",
       "204          笛卡尔树     1\n",
       "\n",
       "[205 rows x 2 columns]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "counts = Counter([actor for actors in alg_tags_df['alg_tags'] for actor in actors])\n",
    "pd.DataFrame([[x, counts[x]] for x in counts], columns=['tag', 'freq']).sort_values(by='freq', ascending=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>support</th>\n",
       "      <th>itemsets</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0.064835</td>\n",
       "      <td>(字符串)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>0.120784</td>\n",
       "      <td>(模拟)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>0.186427</td>\n",
       "      <td>(动态规划,dp)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>0.110887</td>\n",
       "      <td>(枚举)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>0.027671</td>\n",
       "      <td>(递归)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1027</th>\n",
       "      <td>0.001010</td>\n",
       "      <td>(微积分初步, 组合数学, 动态规划,dp)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1028</th>\n",
       "      <td>0.001010</td>\n",
       "      <td>(微积分初步, 递推, 动态规划,dp)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1029</th>\n",
       "      <td>0.001010</td>\n",
       "      <td>(基础算法, 模拟)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1030</th>\n",
       "      <td>0.001010</td>\n",
       "      <td>(构造, Ad-hoc)</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1031</th>\n",
       "      <td>0.000808</td>\n",
       "      <td>(贪心, Ad-hoc)</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>1032 rows × 2 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "       support                itemsets\n",
       "0     0.064835                   (字符串)\n",
       "1     0.120784                    (模拟)\n",
       "2     0.186427               (动态规划,dp)\n",
       "3     0.110887                    (枚举)\n",
       "4     0.027671                    (递归)\n",
       "...        ...                     ...\n",
       "1027  0.001010  (微积分初步, 组合数学, 动态规划,dp)\n",
       "1028  0.001010    (微积分初步, 递推, 动态规划,dp)\n",
       "1029  0.001010              (基础算法, 模拟)\n",
       "1030  0.001010            (构造, Ad-hoc)\n",
       "1031  0.000808            (贪心, Ad-hoc)\n",
       "\n",
       "[1032 rows x 2 columns]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MIN_SUPPORT = 0.0007    #对应最小绝对支持度为4\n",
    "MAX_LEN = 3\n",
    "te = TransactionEncoder()\n",
    "te_ary = te.fit(alg_tags_df['alg_tags']).transform(alg_tags_df['alg_tags'])\n",
    "df = pd.DataFrame(te_ary, columns=te.columns_)\n",
    "\n",
    "freq_df = fpgrowth(df, min_support=MIN_SUPPORT, use_colnames=True, max_len=MAX_LEN)\n",
    "\n",
    "freq_df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>antecedents</th>\n",
       "      <th>consequents</th>\n",
       "      <th>antecedent support</th>\n",
       "      <th>consequent support</th>\n",
       "      <th>support</th>\n",
       "      <th>confidence</th>\n",
       "      <th>lift</th>\n",
       "      <th>leverage</th>\n",
       "      <th>conviction</th>\n",
       "      <th>zhangs_metric</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>(分治, 字符串)</td>\n",
       "      <td>(递归)</td>\n",
       "      <td>0.001212</td>\n",
       "      <td>0.027671</td>\n",
       "      <td>0.000808</td>\n",
       "      <td>0.666667</td>\n",
       "      <td>24.092457</td>\n",
       "      <td>0.000774</td>\n",
       "      <td>2.916986</td>\n",
       "      <td>0.959656</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>(剪枝)</td>\n",
       "      <td>(搜索)</td>\n",
       "      <td>0.011917</td>\n",
       "      <td>0.086649</td>\n",
       "      <td>0.008685</td>\n",
       "      <td>0.728814</td>\n",
       "      <td>8.411086</td>\n",
       "      <td>0.007653</td>\n",
       "      <td>3.367981</td>\n",
       "      <td>0.891736</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>(剪枝, 模拟)</td>\n",
       "      <td>(搜索)</td>\n",
       "      <td>0.001212</td>\n",
       "      <td>0.086649</td>\n",
       "      <td>0.001010</td>\n",
       "      <td>0.833333</td>\n",
       "      <td>9.617327</td>\n",
       "      <td>0.000905</td>\n",
       "      <td>5.480105</td>\n",
       "      <td>0.897108</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>(深度优先搜索,DFS, 剪枝)</td>\n",
       "      <td>(搜索)</td>\n",
       "      <td>0.001414</td>\n",
       "      <td>0.086649</td>\n",
       "      <td>0.001010</td>\n",
       "      <td>0.714286</td>\n",
       "      <td>8.243423</td>\n",
       "      <td>0.000887</td>\n",
       "      <td>3.196728</td>\n",
       "      <td>0.879935</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>(剪枝, 动态规划,dp)</td>\n",
       "      <td>(搜索)</td>\n",
       "      <td>0.001616</td>\n",
       "      <td>0.086649</td>\n",
       "      <td>0.001212</td>\n",
       "      <td>0.750000</td>\n",
       "      <td>8.655594</td>\n",
       "      <td>0.001072</td>\n",
       "      <td>3.653403</td>\n",
       "      <td>0.885899</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>226</th>\n",
       "      <td>(微积分初步)</td>\n",
       "      <td>(组合数学, 动态规划,dp)</td>\n",
       "      <td>0.001414</td>\n",
       "      <td>0.005251</td>\n",
       "      <td>0.001010</td>\n",
       "      <td>0.714286</td>\n",
       "      <td>136.016484</td>\n",
       "      <td>0.001002</td>\n",
       "      <td>3.481620</td>\n",
       "      <td>0.994053</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>227</th>\n",
       "      <td>(微积分初步, 递推)</td>\n",
       "      <td>(动态规划,dp)</td>\n",
       "      <td>0.001010</td>\n",
       "      <td>0.186427</td>\n",
       "      <td>0.001010</td>\n",
       "      <td>1.000000</td>\n",
       "      <td>5.364030</td>\n",
       "      <td>0.000822</td>\n",
       "      <td>inf</td>\n",
       "      <td>0.814395</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>228</th>\n",
       "      <td>(微积分初步, 动态规划,dp)</td>\n",
       "      <td>(递推)</td>\n",
       "      <td>0.001010</td>\n",
       "      <td>0.040800</td>\n",
       "      <td>0.001010</td>\n",
       "      <td>1.000000</td>\n",
       "      <td>24.509901</td>\n",
       "      <td>0.000969</td>\n",
       "      <td>inf</td>\n",
       "      <td>0.960170</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>229</th>\n",
       "      <td>(微积分初步)</td>\n",
       "      <td>(递推, 动态规划,dp)</td>\n",
       "      <td>0.001414</td>\n",
       "      <td>0.013735</td>\n",
       "      <td>0.001010</td>\n",
       "      <td>0.714286</td>\n",
       "      <td>52.006303</td>\n",
       "      <td>0.000990</td>\n",
       "      <td>3.451929</td>\n",
       "      <td>0.982160</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>230</th>\n",
       "      <td>(基础算法)</td>\n",
       "      <td>(模拟)</td>\n",
       "      <td>0.001414</td>\n",
       "      <td>0.120784</td>\n",
       "      <td>0.001010</td>\n",
       "      <td>0.714286</td>\n",
       "      <td>5.913760</td>\n",
       "      <td>0.000839</td>\n",
       "      <td>3.077257</td>\n",
       "      <td>0.832079</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>231 rows × 10 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "          antecedents      consequents  antecedent support  \\\n",
       "0           (分治, 字符串)             (递归)            0.001212   \n",
       "1                (剪枝)             (搜索)            0.011917   \n",
       "2            (剪枝, 模拟)             (搜索)            0.001212   \n",
       "3    (深度优先搜索,DFS, 剪枝)             (搜索)            0.001414   \n",
       "4       (剪枝, 动态规划,dp)             (搜索)            0.001616   \n",
       "..                ...              ...                 ...   \n",
       "226           (微积分初步)  (组合数学, 动态规划,dp)            0.001414   \n",
       "227       (微积分初步, 递推)        (动态规划,dp)            0.001010   \n",
       "228  (微积分初步, 动态规划,dp)             (递推)            0.001010   \n",
       "229           (微积分初步)    (递推, 动态规划,dp)            0.001414   \n",
       "230            (基础算法)             (模拟)            0.001414   \n",
       "\n",
       "     consequent support   support  confidence        lift  leverage  \\\n",
       "0              0.027671  0.000808    0.666667   24.092457  0.000774   \n",
       "1              0.086649  0.008685    0.728814    8.411086  0.007653   \n",
       "2              0.086649  0.001010    0.833333    9.617327  0.000905   \n",
       "3              0.086649  0.001010    0.714286    8.243423  0.000887   \n",
       "4              0.086649  0.001212    0.750000    8.655594  0.001072   \n",
       "..                  ...       ...         ...         ...       ...   \n",
       "226            0.005251  0.001010    0.714286  136.016484  0.001002   \n",
       "227            0.186427  0.001010    1.000000    5.364030  0.000822   \n",
       "228            0.040800  0.001010    1.000000   24.509901  0.000969   \n",
       "229            0.013735  0.001010    0.714286   52.006303  0.000990   \n",
       "230            0.120784  0.001010    0.714286    5.913760  0.000839   \n",
       "\n",
       "     conviction  zhangs_metric  \n",
       "0      2.916986       0.959656  \n",
       "1      3.367981       0.891736  \n",
       "2      5.480105       0.897108  \n",
       "3      3.196728       0.879935  \n",
       "4      3.653403       0.885899  \n",
       "..          ...            ...  \n",
       "226    3.481620       0.994053  \n",
       "227         inf       0.814395  \n",
       "228         inf       0.960170  \n",
       "229    3.451929       0.982160  \n",
       "230    3.077257       0.832079  \n",
       "\n",
       "[231 rows x 10 columns]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MIN_CONFIDENCE = 0.65\n",
    "alg_tag_rules = association_rules(freq_df, metric=\"confidence\", min_threshold=MIN_CONFIDENCE)\n",
    "\n",
    "alg_tag_rules"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def format_set(set_x):\n",
    "    return str(set_x).replace('frozenset({', '').replace('})', '').replace('\\'', '').replace(', ', '&')\n",
    "\n",
    "\n",
    "alg_tag_rules['antecedents'] = alg_tag_rules['antecedents'].apply(lambda x: format_set(x))\n",
    "alg_tag_rules['consequents'] = alg_tag_rules['consequents'].apply(lambda x: format_set(x))\n",
    "\n",
    "alg_tag_rules.to_csv('sup{}-conf{}-maxlen{}-rules.csv'.format(MIN_SUPPORT, MIN_SUPPORT, MAX_LEN))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
